1. Field of the Invention
This invention relates generally to classifying and sorting systems and, more specifically, to a system for sorting alphanumeric character strings or other types of data having preassigned hierarchal value systems.
2. Prior Art
One of the most common uses for computer systems is sorting. Sorting numeric strings, such as zip codes, allows addresses to be grouped by zip code for more convenient handling of the mail. Sorting alphabetical strings, such as people's last names, allows the printing of directories in alphabetical order.
An important advantage of using a computer for sorting is that computers can sort faster than a person can sort by hand. But even computers take time to sort. Depending on how long the list is, a sorting process may take from several seconds to several minutes. Computer programmers have developed several methods for sorting by computer. Some methods are faster and some methods are slower. People keep trying to find faster methods of sorting.
The operation of one, known prior art technique uses compares. A compare is an operation that compares two items to determine which is "greater" and which is "lesser". Typically, a word beginning with "A" is lesser (i.e. has a different value on a scale such as the alphabet) than a word beginning with "B". If the lesser word comes after the greater word in the list, then the word is out of order. After the compare operation, the words are put into their proper order. According to the operation of prior art, computers have no way of knowing how to order a list of items without using compares.
A major shortcoming of using compares is that the longer the list, the longer the sorting time. A list of two items requires only one compare, namely the comparison between the two items. But a list of three items requires that the first item be compared to each of the other two, and the remaining two items need to be compared to each other, for a total of three compares. Therefore, increasing the length of the list multiplies the number of compares. The larger the list, the larger is the multiplication of compares. Adding just one item to a list of 100 items does not require just one more compare, but rather it requires that the additional item be compared in some way to each of the other 100 items. Adding only one item to a list 1,000 long requires up to 1,000 additional compares. A formula which calculates the number of compares is N.times.N/2, where N is the number of items in the list. Prior methods have devised shortcuts to reduce the number of compares somewhat. This has resulted in an improved formula, N.times.log(base 2) (N), where N is the number of items in the list. But all of these methods, even the most improved methods, still work under the same mathematical disadvantage of the compare method of sorting.